/*
https://leetcode-cn.com/problems/perfect-rectangle/solution/wan-mei-ju-xing-by-leetcode-solution-ty8q/
 */
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution391 {
    public boolean isRectangleCover(int[][] rectangles) {
        Map<List<Integer>,Integer> map=new HashMap<>();
        int xMin=Integer.MAX_VALUE,xMax=Integer.MIN_VALUE;
        int yMin=xMin,yMax=xMax;
        int s=0;
        for (int[] rectangle : rectangles) {
            List<Integer> f1=new ArrayList<>();
            f1.add(rectangle[0]);f1.add(rectangle[1]);
            List<Integer> f2=new ArrayList<>();
            f2.add(rectangle[0]);f2.add(rectangle[3]);
            List<Integer> f3=new ArrayList<>();
            f3.add(rectangle[2]);f3.add(rectangle[1]);
            List<Integer> f4=new ArrayList<>();
            f4.add(rectangle[2]);f4.add(rectangle[3]);
            map.put(f1,map.getOrDefault(f1,0)+1);
            map.put(f2,map.getOrDefault(f2,0)+1);
            map.put(f3,map.getOrDefault(f3,0)+1);
            map.put(f4,map.getOrDefault(f4,0)+1);
            xMin=Math.min(xMin,rectangle[0]);
            yMin=Math.min(yMin,rectangle[1]);
            xMax=Math.max(xMax,rectangle[2]);
            yMax=Math.max(yMax,rectangle[3]);
            s+=(rectangle[2]-rectangle[0])*(rectangle[3]-rectangle[1]);
        }
        if ((xMax-xMin)*(yMax-yMin)!=s){
            return false;
        }
        for (Map.Entry<List<Integer>,Integer> entry:map.entrySet()){
            List<Integer> i=entry.getKey();
            if ((i.get(0)==xMin||i.get(0)==xMax)&&(i.get(1)==yMin||i.get(1)==yMax)){
                if (entry.getValue()==1){
                    continue;
                }else{
                    return false;
                }
            }
            if (entry.getValue()==2||entry.getValue()==4){
                continue;
            }
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new Solution391().isRectangleCover(new int[][]{{1,1,3,3},{3,1,4,2},{3,2,4,4},{1,3,2,4},{2,3,3,4}}));
    }
}
